/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/fast-power
@Language: C++
@Datetime: 16-02-09 05:49
*/

class Solution {
public:
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    int fastPower(int a, int b, int n) {
        // write your code here
        long long res=1,r=a;
        if (n==0){
            r=a=1;
            res = a%b;
        }
    	for(;n;n>>=1){
            if(n&1)
                res=(res*r)%b;
            r=(r*r)%b;
    	}
    	return res;
    }
};